package com.zang.greedy;

/**
 * @author ZVerify
 * @since 2022/11/21 19:43
 **/
public class 跳跃游戏II {

    public int jump(int[] nums) {

        if (nums == null || nums.length == 0 || nums.length == 1) return 0;

        // 跳跃次数
        int count = 0;
        // 当前的最大区域
        int curDistance = 0;
        // 最大的区域
        int maxDistance = 0;

        for (int i = 0; i < nums.length; i++) {

            // 当前的最远距离，后续来的时候都是当前格的最大距离
            maxDistance = Math.max(maxDistance, i+nums[i]);

            // 可以调到外边了加上当前这步直接出去
            if (maxDistance >= nums.length-1) {
                count++;
                break;
            }
            // 首先第一初始化一定会走这个if然后得到第一步的最大距离
            // 后续只有到达下一步的最远的时候，把我下一步最远的路程替换掉当前的最远路程
            if (i == curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}
